package com.zhouhong;
/**
 * @ClassName: selection-sort
 * @Description: 选择排序
 * @Author: zhouhong
 * @Create: 2021-03-28 17:59
 **/
public class SelectionSort {

    private SelectionSort(){}
    /**
     * 思路：（每次找到最小的数字，将它放到当前第一个位置，不包括之前放好的数字）
     * 使用两个指针（标志），都从数组 0 开始，外层  i 循环遍历整个数组，
     * 内层：j 每次从 i 开始向后遍历，找到里面最小的数字，然后交换最小数字跟 i 位置的数字
     * 时间复杂度：O(n^2)，空间复杂度：O(1)
    */
    public static <E extends Comparable<E>> void sort1(E[] arr){
        for (int i = 0; i < arr.length; i++) {
            // 选择 arr[i....n) 中的最小值的索引
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if ( arr[j].compareTo(arr[minIndex]) < 0){
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    // 换一种思路，把最大的放到后面
    public static <E extends Comparable<E>> void sort2(E[] arr){
        for (int i = arr.length - 1; i >= 0; i--) {
            // 选择 arr[i....n) 中的最大值的索引
            int maxIndex = i;
            for (int j = i; j >= 0; j--) {
                if ( arr[j].compareTo(arr[maxIndex]) > 0){
                    maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }

    // 交换位置
    private static <E> void swap(E[] arr, int i, int j){
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n:dataSize) {
            Integer[] num = ArrayGenerator.generatorRandomArray(n,n);
            SortingHelper.sortTest("SelectionSort", num);
        }
    }
}
